home *** CD-ROM | disk | FTP | other *** search
/ Disc to the Future 2 / Disc to the Future Part II Programmer's Reference (Wayzata Technology)(6013)(1992).bin / MAC / THINKC / 4_0 / FLEX-TC_ / TBLCMP.C < prev    next >
Text File  |  1990-01-02  |  25KB  |  920 lines
  1. /* tblcmp - table compression routines */
  2.  
  3. /*
  4.  * Copyright (c) 1989 The Regents of the University of California.
  5.  * All rights reserved.
  6.  *
  7.  * This code is derived from software contributed to Berkeley by
  8.  * Vern Paxson.
  9.  * 
  10.  * The United States Government has rights in this work pursuant to
  11.  * contract no. DE-AC03-76SF00098 between the United States Department of
  12.  * Energy and the University of California.
  13.  *
  14.  * Redistribution and use in source and binary forms are permitted
  15.  * provided that the above copyright notice and this paragraph are
  16.  * duplicated in all such forms and that any documentation,
  17.  * advertising materials, and other materials related to such
  18.  * distribution and use acknowledge that the software was developed
  19.  * by the University of California, Berkeley.  The name of the
  20.  * University may not be used to endorse or promote products derived
  21.  * from this software without specific prior written permission.
  22.  * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
  23.  * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
  24.  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
  25.  */
  26.  
  27. #ifndef lint
  28.  
  29. static char copyright[] =
  30.     "@(#) Copyright (c) 1989 The Regents of the University of California.\n";
  31. static char CR_continuation[] = "@(#) All rights reserved.\n";
  32.  
  33. static char rcsid[] =
  34.     "@(#) $Header: tblcmp.c,v 2.0 89/06/20 15:50:21 vern Locked $ (LBL)";
  35.  
  36. #endif
  37.  
  38. #include "flexdef.h"
  39.  
  40. /* bldtbl - build table entries for dfa state
  41.  *
  42.  * synopsis
  43.  *   int state[numecs], statenum, totaltrans, comstate, comfreq;
  44.  *   bldtbl( state, statenum, totaltrans, comstate, comfreq );
  45.  *
  46.  * State is the statenum'th dfa state.  It is indexed by equivalence class and
  47.  * gives the number of the state to enter for a given equivalence class.
  48.  * totaltrans is the total number of transitions out of the state.  Comstate
  49.  * is that state which is the destination of the most transitions out of State.
  50.  * Comfreq is how many transitions there are out of State to Comstate.
  51.  *
  52.  * A note on terminology:
  53.  *    "protos" are transition tables which have a high probability of
  54.  * either being redundant (a state processed later will have an identical
  55.  * transition table) or nearly redundant (a state processed later will have
  56.  * many of the same out-transitions).  A "most recently used" queue of
  57.  * protos is kept around with the hope that most states will find a proto
  58.  * which is similar enough to be usable, and therefore compacting the
  59.  * output tables.
  60.  *    "templates" are a special type of proto.  If a transition table is
  61.  * homogeneous or nearly homogeneous (all transitions go to the same
  62.  * destination) then the odds are good that future states will also go
  63.  * to the same destination state on basically the same character set.
  64.  * These homogeneous states are so common when dealing with large rule
  65.  * sets that they merit special attention.  If the transition table were
  66.  * simply made into a proto, then (typically) each subsequent, similar
  67.  * state will differ from the proto for two out-transitions.  One of these
  68.  * out-transitions will be that character on which the proto does not go
  69.  * to the common destination, and one will be that character on which the
  70.  * state does not go to the common destination.  Templates, on the other
  71.  * hand, go to the common state on EVERY transition character, and therefore
  72.  * cost only one difference.
  73.  */
  74.  
  75. bldtbl( state, statenum, totaltrans, comstate, comfreq )
  76. int state[], statenum, totaltrans, comstate, comfreq;
  77.  
  78.     {
  79.     int extptr, extrct[2][CSIZE + 1];
  80.     int mindiff, minprot, i, d;
  81.     int checkcom;
  82.  
  83.     /* If extptr is 0 then the first array of extrct holds the result of the
  84.      * "best difference" to date, which is those transitions which occur in
  85.      * "state" but not in the proto which, to date, has the fewest differences
  86.      * between itself and "state".  If extptr is 1 then the second array of
  87.      * extrct hold the best difference.  The two arrays are toggled
  88.      * between so that the best difference to date can be kept around and
  89.      * also a difference just created by checking against a candidate "best"
  90.      * proto.
  91.      */
  92.  
  93.     extptr = 0;
  94.  
  95.     /* if the state has too few out-transitions, don't bother trying to
  96.      * compact its tables
  97.      */
  98.  
  99.     if ( (totaltrans * 100) < (numecs * PROTO_SIZE_PERCENTAGE) )
  100.     mkentry( state, numecs, statenum, JAMSTATE, totaltrans );
  101.  
  102.     else
  103.     {
  104.     /* checkcom is true if we should only check "state" against
  105.      * protos which have the same "comstate" value
  106.      */
  107.  
  108.     checkcom = comfreq * 100 > totaltrans * CHECK_COM_PERCENTAGE;
  109.  
  110.     minprot = firstprot;
  111.     mindiff = totaltrans;
  112.  
  113.     if ( checkcom )
  114.         {
  115.         /* find first proto which has the same "comstate" */
  116.         for ( i = firstprot; i != NIL; i = protnext[i] )
  117.         if ( protcomst[i] == comstate )
  118.             {
  119.             minprot = i;
  120.             mindiff = tbldiff( state, minprot, extrct[extptr] );
  121.             break;
  122.             }
  123.         }
  124.  
  125.     else
  126.         {
  127.         /* since we've decided that the most common destination out
  128.          * of "state" does not occur with a high enough frequency,
  129.          * we set the "comstate" to zero, assuring that if this state
  130.          * is entered into the proto list, it will not be considered
  131.          * a template.
  132.          */
  133.         comstate = 0;
  134.  
  135.         if ( firstprot != NIL )
  136.         {
  137.         minprot = firstprot;
  138.         mindiff = tbldiff( state, minprot, extrct[extptr] );
  139.         }
  140.         }
  141.  
  142.     /* we now have the first interesting proto in "minprot".  If
  143.      * it matches within the tolerances set for the first proto,
  144.      * we don't want to bother scanning the rest of the proto list
  145.      * to see if we have any other reasonable matches.
  146.      */
  147.  
  148.     if ( mindiff * 100 > totaltrans * FIRST_MATCH_DIFF_PERCENTAGE )
  149.         { /* not a good enough match.  Scan the rest of the protos */
  150.         for ( i = minprot; i != NIL; i = protnext[i] )
  151.         {
  152.         d = tbldiff( state, i, extrct[1 - extptr] );
  153.         if ( d < mindiff )
  154.             {
  155.             extptr = 1 - extptr;
  156.             mindiff = d;
  157.             minprot = i;
  158.             }
  159.         }
  160.         }
  161.  
  162.     /* check if the proto we've decided on as our best bet is close
  163.      * enough to the state we want to match to be usable
  164.      */
  165.  
  166.     if ( mindiff * 100 > totaltrans * ACCEPTABLE_DIFF_PERCENTAGE )
  167.         {
  168.         /* no good.  If the state is homogeneous enough, we make a
  169.          * template out of it.  Otherwise, we make a proto.
  170.          */
  171.  
  172.         if ( comfreq * 100 >= totaltrans * TEMPLATE_SAME_PERCENTAGE )
  173.         mktemplate( state, statenum, comstate );
  174.  
  175.         else
  176.         {
  177.         mkprot( state, statenum, comstate );
  178.         mkentry( state, numecs, statenum, JAMSTATE, totaltrans );
  179.         }
  180.         }
  181.  
  182.     else
  183.         { /* use the proto */
  184.         mkentry( extrct[extptr], numecs, statenum,
  185.              prottbl[minprot], mindiff );
  186.  
  187.         /* if this state was sufficiently different from the proto
  188.          * we built it from, make it, too, a proto
  189.          */
  190.  
  191.         if ( mindiff * 100 >= totaltrans * NEW_PROTO_DIFF_PERCENTAGE )
  192.         mkprot( state, statenum, comstate );
  193.  
  194.         /* since mkprot added a new proto to the proto queue, it's possible
  195.          * that "minprot" is no longer on the proto queue (if it happened
  196.          * to have been the last entry, it would have been bumped off).
  197.          * If it's not there, then the new proto took its physical place
  198.          * (though logically the new proto is at the beginning of the
  199.          * queue), so in that case the following call will do nothing.
  200.          */
  201.  
  202.         mv2front( minprot );
  203.         }
  204.     }
  205.     }
  206.  
  207.  
  208. /* cmptmps - compress template table entries
  209.  *
  210.  * synopsis
  211.  *    cmptmps();
  212.  *
  213.  *  template tables are compressed by using the 'template equivalence
  214.  *  classes', which are collections of transition character equivalence
  215.  *  classes which always appear together in templates - really meta-equivalence
  216.  *  classes.  until this point, the tables for templates have been stored
  217.  *  up at the top end of the nxt array; they will now be compressed and have
  218.  *  table entries made for them.
  219.  */
  220.  
  221. cmptmps()
  222.  
  223.     {
  224.     int tmpstorage[CSIZE + 1];
  225.     register int *tmp = tmpstorage, i, j;
  226.     int totaltrans, trans;
  227.  
  228.     peakpairs = numtemps * numecs + tblend;
  229.  
  230.     if ( usemecs )
  231.     {
  232.     /* create equivalence classes base on data gathered on template
  233.      * transitions
  234.      */
  235.  
  236.     nummecs = cre8ecs( tecfwd, tecbck, numecs );
  237.     }
  238.     
  239.     else
  240.     nummecs = numecs;
  241.  
  242.     if ( lastdfa + numtemps + 1 >= current_max_dfas )
  243.     increase_max_dfas();
  244.  
  245.     /* loop through each template */
  246.  
  247.     for ( i = 1; i <= numtemps; ++i )
  248.     {
  249.     totaltrans = 0;    /* number of non-jam transitions out of this template */
  250.  
  251.     for ( j = 1; j <= numecs; ++j )
  252.         {
  253.         trans = tnxt[numecs * i + j];
  254.  
  255.         if ( usemecs )
  256.         {
  257.         /* the absolute value of tecbck is the meta-equivalence class
  258.          * of a given equivalence class, as set up by cre8ecs
  259.          */
  260.         if ( tecbck[j] > 0 )
  261.             {
  262.             tmp[tecbck[j]] = trans;
  263.  
  264.             if ( trans > 0 )
  265.             ++totaltrans;
  266.             }
  267.         }
  268.  
  269.         else
  270.         {
  271.         tmp[j] = trans;
  272.  
  273.         if ( trans > 0 )
  274.             ++totaltrans;
  275.         }
  276.         }
  277.  
  278.     /* it is assumed (in a rather subtle way) in the skeleton that
  279.      * if we're using meta-equivalence classes, the def[] entry for
  280.      * all templates is the jam template, i.e., templates never default
  281.      * to other non-jam table entries (e.g., another template)
  282.      */
  283.  
  284.     /* leave room for the jam-state after the last real state */
  285.     mkentry( tmp, nummecs, lastdfa + i + 1, JAMSTATE, totaltrans );
  286.     }
  287.     }
  288.  
  289.  
  290.  
  291. /* expand_nxt_chk - expand the next check arrays */
  292.  
  293. expand_nxt_chk()
  294.  
  295.     {
  296.     register int old_max = current_max_xpairs;
  297.  
  298.     current_max_xpairs += MAX_XPAIRS_INCREMENT;
  299.  
  300.     ++num_reallocs;
  301.  
  302.     nxt = reallocate_integer_array( nxt, current_max_xpairs );
  303.     chk = reallocate_integer_array( chk, current_max_xpairs );
  304.  
  305.     bzero( (char *) (chk + old_max),
  306.        MAX_XPAIRS_INCREMENT * sizeof( int ) / sizeof( char ) );
  307.     }
  308.  
  309.  
  310. /* find_table_space - finds a space in the table for a state to be placed
  311.  *
  312.  * synopsis
  313.  *     int *state, numtrans, block_start;
  314.  *     int find_table_space();
  315.  *
  316.  *     block_start = find_table_space( state, numtrans );
  317.  *
  318.  * State is the state to be added to the full speed transition table.
  319.  * Numtrans is the number of out-transitions for the state.
  320.  *
  321.  * find_table_space() returns the position of the start of the first block (in
  322.  * chk) able to accommodate the state
  323.  *
  324.  * In determining if a state will or will not fit, find_table_space() must take
  325.  * into account the fact that an end-of-buffer state will be added at [0],
  326.  * and an action number will be added in [-1].
  327.  */
  328.  
  329. int find_table_space( state, numtrans )
  330. int *state, numtrans;
  331.     
  332.     {
  333.     /* firstfree is the position of the first possible occurrence of two
  334.      * consecutive unused records in the chk and nxt arrays
  335.      */
  336.     register int i;
  337.     register int *state_ptr, *chk_ptr;
  338.     register int *ptr_to_last_entry_in_state;
  339.  
  340.     /* if there are too many out-transitions, put the state at the end of
  341.      * nxt and chk
  342.      */
  343.     if ( numtrans > MAX_XTIONS_FULL_INTERIOR_FIT )
  344.     {
  345.     /* if table is empty, return the first available spot in chk/nxt,
  346.      * which should be 1
  347.      */
  348.     if ( tblend < 2 )
  349.         return ( 1 );
  350.  
  351.     i = tblend - numecs;    /* start searching for table space near the
  352.                  * end of chk/nxt arrays
  353.                  */
  354.     }
  355.  
  356.     else
  357.     i = firstfree;        /* start searching for table space from the
  358.                  * beginning (skipping only the elements
  359.                  * which will definitely not hold the new
  360.                  * state)
  361.                  */
  362.  
  363.     while ( 1 )        /* loops until a space is found */
  364.     {
  365.     if ( i + numecs > current_max_xpairs )
  366.         expand_nxt_chk();
  367.  
  368.     /* loops until space for end-of-buffer and action number are found */
  369.     while ( 1 )
  370.         {
  371.         if ( chk[i - 1] == 0 )    /* check for action number space */
  372.         {
  373.         if ( chk[i] == 0 )    /* check for end-of-buffer space */
  374.             break;
  375.  
  376.         else
  377.             i += 2;    /* since i != 0, there is no use checking to
  378.                  * see if (++i) - 1 == 0, because that's the
  379.                  * same as i == 0, so we skip a space
  380.                  */
  381.         }
  382.  
  383.         else
  384.         ++i;
  385.  
  386.         if ( i + numecs > current_max_xpairs )
  387.         expand_nxt_chk();
  388.         }
  389.  
  390.     /* if we started search from the beginning, store the new firstfree for
  391.      * the next call of find_table_space()
  392.      */
  393.     if ( numtrans <= MAX_XTIONS_FULL_INTERIOR_FIT )
  394.         firstfree = i + 1;
  395.  
  396.     /* check to see if all elements in chk (and therefore nxt) that are
  397.      * needed for the new state have not yet been taken
  398.      */
  399.  
  400.     state_ptr = &state[1];
  401.     ptr_to_last_entry_in_state = &chk[i + numecs + 1];
  402.  
  403.     for ( chk_ptr = &chk[i + 1]; chk_ptr != ptr_to_last_entry_in_state;
  404.           ++chk_ptr )
  405.         if ( *(state_ptr++) != 0 && *chk_ptr != 0 )
  406.         break;
  407.  
  408.     if ( chk_ptr == ptr_to_last_entry_in_state )
  409.         return ( i );
  410.  
  411.     else
  412.         ++i;
  413.     }
  414.     }
  415.  
  416.  
  417. /* inittbl - initialize transition tables
  418.  *
  419.  * synopsis
  420.  *   inittbl();
  421.  *
  422.  * Initializes "firstfree" to be one beyond the end of the table.  Initializes
  423.  * all "chk" entries to be zero.  Note that templates are built in their
  424.  * own tbase/tdef tables.  They are shifted down to be contiguous
  425.  * with the non-template entries during table generation.
  426.  */
  427. inittbl()
  428.  
  429.     {
  430.     register int i;
  431.  
  432.     bzero( (char *) chk, current_max_xpairs * sizeof( int ) / sizeof( char ) );
  433.  
  434.     tblend = 0;
  435.     firstfree = tblend + 1;
  436.     numtemps = 0;
  437.  
  438.     if ( usemecs )
  439.     {
  440.     /* set up doubly-linked meta-equivalence classes
  441.      * these are sets of equivalence classes which all have identical
  442.      * transitions out of TEMPLATES
  443.      */
  444.  
  445.     tecbck[1] = NIL;
  446.  
  447.     for ( i = 2; i <= numecs; ++i )
  448.         {
  449.         tecbck[i] = i - 1;
  450.         tecfwd[i - 1] = i;
  451.         }
  452.  
  453.     tecfwd[numecs] = NIL;
  454.     }
  455.     }
  456.  
  457.  
  458. /* mkdeftbl - make the default, "jam" table entries
  459.  *
  460.  * synopsis
  461.  *   mkdeftbl();
  462.  */
  463.  
  464. mkdeftbl()
  465.  
  466.     {
  467.     int i;
  468.  
  469.     jamstate = lastdfa + 1;
  470.  
  471.     ++tblend; /* room for transition on end-of-buffer character */
  472.  
  473.     if ( tblend + numecs > current_max_xpairs )
  474.     expand_nxt_chk();
  475.  
  476.     /* add in default end-of-buffer transition */
  477.     nxt[tblend] = end_of_buffer_state;
  478.     chk[tblend] = jamstate;
  479.  
  480.     for ( i = 1; i <= numecs; ++i )
  481.     {
  482.     nxt[tblend + i] = 0;
  483.     chk[tblend + i] = jamstate;
  484.     }
  485.  
  486.     jambase = tblend;
  487.  
  488.     base[jamstate] = jambase;
  489.     def[jamstate] = 0;
  490.  
  491.     tblend += numecs;
  492.     ++numtemps;
  493.     }
  494.  
  495.  
  496. /* mkentry - create base/def and nxt/chk entries for transition array
  497.  *
  498.  * synopsis
  499.  *   int state[numchars + 1], numchars, statenum, deflink, totaltrans;
  500.  *   mkentry( state, numchars, statenum, deflink, totaltrans );
  501.  *
  502.  * "state" is a transition array "numchars" characters in size, "statenum"
  503.  * is the offset to be used into the base/def tables, and "deflink" is the
  504.  * entry to put in the "def" table entry.  If "deflink" is equal to
  505.  * "JAMSTATE", then no attempt will be made to fit zero entries of "state"
  506.  * (i.e., jam entries) into the table.  It is assumed that by linking to
  507.  * "JAMSTATE" they will be taken care of.  In any case, entries in "state"
  508.  * marking transitions to "SAME_TRANS" are treated as though they will be
  509.  * taken care of by whereever "deflink" points.  "totaltrans" is the total
  510.  * number of transitions out of the state.  If it is below a certain threshold,
  511.  * the tables are searched for an interior spot that will accommodate the
  512.  * state array.
  513.  */
  514.  
  515. mkentry( state, numchars, statenum, deflink, totaltrans )
  516. register int *state;
  517. int numchars, statenum, deflink, totaltrans;
  518.  
  519.     {
  520.     register int minec, maxec, i, baseaddr;
  521.     int tblbase, tbllast;
  522.  
  523.     if ( totaltrans == 0 )
  524.     { /* there are no out-transitions */
  525.     if ( deflink == JAMSTATE )
  526.         base[statenum] = JAMSTATE;
  527.     else
  528.         base[statenum] = 0;
  529.  
  530.     def[statenum] = deflink;
  531.     return;
  532.     }
  533.  
  534.     for ( minec = 1; minec <= numchars; ++minec )
  535.     {
  536.     if ( state[minec] != SAME_TRANS )
  537.         if ( state[minec] != 0 || deflink != JAMSTATE )
  538.         break;
  539.     }
  540.  
  541.     if ( totaltrans == 1 )
  542.     {
  543.     /* there's only one out-transition.  Save it for later to fill
  544.      * in holes in the tables.
  545.      */
  546.     stack1( statenum, minec, state[minec], deflink );
  547.     return;
  548.     }
  549.  
  550.     for ( maxec = numchars; maxec > 0; --maxec )
  551.     {
  552.     if ( state[maxec] != SAME_TRANS )
  553.         if ( state[maxec] != 0 || deflink != JAMSTATE )
  554.         break;
  555.     }
  556.  
  557.     /* Whether we try to fit the state table in the middle of the table
  558.      * entries we have already generated, or if we just take the state
  559.      * table at the end of the nxt/chk tables, we must make sure that we
  560.      * have a valid base address (i.e., non-negative).  Note that not only are
  561.      * negative base addresses dangerous at run-time (because indexing the
  562.      * next array with one and a low-valued character might generate an
  563.      * array-out-of-bounds error message), but at compile-time negative
  564.      * base addresses denote TEMPLATES.
  565.      */
  566.  
  567.     /* find the first transition of state that we need to worry about. */
  568.     if ( totaltrans * 100 <= numchars * INTERIOR_FIT_PERCENTAGE )
  569.     { /* attempt to squeeze it into the middle of the tabls */
  570.     baseaddr = firstfree;
  571.  
  572.     while ( baseaddr < minec )
  573.         {
  574.         /* using baseaddr would result in a negative base address below
  575.          * find the next free slot
  576.          */
  577.         for ( ++baseaddr; chk[baseaddr] != 0; ++baseaddr )
  578.         ;
  579.         }
  580.  
  581.     if ( baseaddr + maxec - minec >= current_max_xpairs )
  582.         expand_nxt_chk();
  583.  
  584.     for ( i = minec; i <= maxec; ++i )
  585.         if ( state[i] != SAME_TRANS )
  586.         if ( state[i] != 0 || deflink != JAMSTATE )
  587.             if ( chk[baseaddr + i - minec] != 0 )
  588.             { /* baseaddr unsuitable - find another */
  589.             for ( ++baseaddr;
  590.                   baseaddr < current_max_xpairs &&
  591.                   chk[baseaddr] != 0;
  592.                   ++baseaddr )
  593.                 ;
  594.  
  595.             if ( baseaddr + maxec - minec >= current_max_xpairs )
  596.                 expand_nxt_chk();
  597.  
  598.             /* reset the loop counter so we'll start all
  599.              * over again next time it's incremented
  600.              */
  601.  
  602.             i = minec - 1;
  603.             }
  604.     }
  605.  
  606.     else
  607.     {
  608.     /* ensure that the base address we eventually generate is
  609.      * non-negative
  610.      */
  611.     baseaddr = max( tblend + 1, minec );
  612.     }
  613.  
  614.     tblbase = baseaddr - minec;
  615.     tbllast = tblbase + maxec;
  616.  
  617.     if ( tbllast >= current_max_xpairs )
  618.     expand_nxt_chk();
  619.  
  620.     base[statenum] = tblbase;
  621.     def[statenum] = deflink;
  622.  
  623.     for ( i = minec; i <= maxec; ++i )
  624.     if ( state[i] != SAME_TRANS )
  625.         if ( state[i] != 0 || deflink != JAMSTATE )
  626.         {
  627.         nxt[tblbase + i] = state[i];
  628.         chk[tblbase + i] = statenum;
  629.         }
  630.  
  631.     if ( baseaddr == firstfree )
  632.     /* find next free slot in tables */
  633.     for ( ++firstfree; chk[firstfree] != 0; ++firstfree )
  634.         ;
  635.  
  636.     tblend = max( tblend, tbllast );
  637.     }
  638.  
  639.  
  640. /* mk1tbl - create table entries for a state (or state fragment) which
  641.  *            has only one out-transition
  642.  *
  643.  * synopsis
  644.  *   int state, sym, onenxt, onedef;
  645.  *   mk1tbl( state, sym, onenxt, onedef );
  646.  */
  647.  
  648. mk1tbl( state, sym, onenxt, onedef )
  649. int state, sym, onenxt, onedef;
  650.  
  651.     {
  652.     if ( firstfree < sym )
  653.     firstfree = sym;
  654.  
  655.     while ( chk[firstfree] != 0 )
  656.     if ( ++firstfree >= current_max_xpairs )
  657.         expand_nxt_chk();
  658.  
  659.     base[state] = firstfree - sym;
  660.     def[state] = onedef;
  661.     chk[firstfree] = state;
  662.     nxt[firstfree] = onenxt;
  663.  
  664.     if ( firstfree > tblend )
  665.     {
  666.     tblend = firstfree++;
  667.  
  668.     if ( firstfree >= current_max_xpairs )
  669.         expand_nxt_chk();
  670.     }
  671.     }
  672.  
  673.  
  674. /* mkprot - create new proto entry
  675.  *
  676.  * synopsis
  677.  *   int state[], statenum, comstate;
  678.  *   mkprot( state, statenum, comstate );
  679.  */
  680.  
  681. mkprot( state, statenum, comstate )
  682. int state[], statenum, comstate;
  683.  
  684.     {
  685.     int i, slot, tblbase;
  686.  
  687.     if ( ++numprots >= MSP || numecs * numprots >= PROT_SAVE_SIZE )
  688.     {
  689.     /* gotta make room for the new proto by dropping last entry in
  690.      * the queue
  691.      */
  692.     slot = lastprot;
  693.     lastprot = protprev[lastprot];
  694.     protnext[lastprot] = NIL;
  695.     }
  696.  
  697.     else
  698.     slot = numprots;
  699.  
  700.     protnext[slot] = firstprot;
  701.  
  702.     if ( firstprot != NIL )
  703.     protprev[firstprot] = slot;
  704.  
  705.     firstprot = slot;
  706.     prottbl[slot] = statenum;
  707.     protcomst[slot] = comstate;
  708.  
  709.     /* copy state into save area so it can be compared with rapidly */
  710.     tblbase = numecs * (slot - 1);
  711.  
  712.     for ( i = 1; i <= numecs; ++i )
  713.     protsave[tblbase + i] = state[i];
  714.     }
  715.  
  716.  
  717. /* mktemplate - create a template entry based on a state, and connect the state
  718.  *              to it
  719.  *
  720.  * synopsis
  721.  *   int state[], statenum, comstate, totaltrans;
  722.  *   mktemplate( state, statenum, comstate, totaltrans );
  723.  */
  724.  
  725. mktemplate( state, statenum, comstate )
  726. int state[], statenum, comstate;
  727.  
  728.     {
  729.     int i, numdiff, tmpbase, tmp[CSIZE + 1];
  730.     char transset[CSIZE + 1];
  731.     int tsptr;
  732.  
  733.     ++numtemps;
  734.  
  735.     tsptr = 0;
  736.  
  737.     /* calculate where we will temporarily store the transition table
  738.      * of the template in the tnxt[] array.  The final transition table
  739.      * gets created by cmptmps()
  740.      */
  741.  
  742.     tmpbase = numtemps * numecs;
  743.  
  744.     if ( tmpbase + numecs >= current_max_template_xpairs )
  745.     {
  746.     current_max_template_xpairs += MAX_TEMPLATE_XPAIRS_INCREMENT;
  747.  
  748.     ++num_reallocs;
  749.  
  750.     tnxt = reallocate_integer_array( tnxt, current_max_template_xpairs );
  751.     }
  752.  
  753.     for ( i = 1; i <= numecs; ++i )
  754.     if ( state[i] == 0 )
  755.         tnxt[tmpbase + i] = 0;
  756.     else
  757.         {
  758.         transset[tsptr++] = i;
  759.         tnxt[tmpbase + i] = comstate;
  760.         }
  761.  
  762.     if ( usemecs )
  763.     mkeccl( transset, tsptr, tecfwd, tecbck, numecs );
  764.  
  765.     mkprot( tnxt + tmpbase, -numtemps, comstate );
  766.  
  767.     /* we rely on the fact that mkprot adds things to the beginning
  768.      * of the proto queue
  769.      */
  770.  
  771.     numdiff = tbldiff( state, firstprot, tmp );
  772.     mkentry( tmp, numecs, statenum, -numtemps, numdiff );
  773.     }
  774.  
  775.  
  776. /* mv2front - move proto queue element to front of queue
  777.  *
  778.  * synopsis
  779.  *   int qelm;
  780.  *   mv2front( qelm );
  781.  */
  782.  
  783. mv2front( qelm )
  784. int qelm;
  785.  
  786.     {
  787.     if ( firstprot != qelm )
  788.     {
  789.     if ( qelm == lastprot )
  790.         lastprot = protprev[lastprot];
  791.  
  792.     protnext[protprev[qelm]] = protnext[qelm];
  793.  
  794.     if ( protnext[qelm] != NIL )
  795.         protprev[protnext[qelm]] = protprev[qelm];
  796.  
  797.     protprev[qelm] = NIL;
  798.     protnext[qelm] = firstprot;
  799.     protprev[firstprot] = qelm;
  800.     firstprot = qelm;
  801.     }
  802.     }
  803.  
  804.  
  805. /* place_state - place a state into full speed transition table
  806.  *
  807.  * synopsis
  808.  *     int *state, statenum, transnum;
  809.  *     place_state( state, statenum, transnum );
  810.  *
  811.  * State is the statenum'th state.  It is indexed by equivalence class and
  812.  * gives the number of the state to enter for a given equivalence class.
  813.  * Transnum is the number of out-transitions for the state.
  814.  */
  815.  
  816. place_state( state, statenum, transnum )
  817. int *state, statenum, transnum;
  818.  
  819.     {
  820.     register int i;
  821.     register int *state_ptr;
  822.     int position = find_table_space( state, transnum );
  823.  
  824.     /* base is the table of start positions */
  825.     base[statenum] = position;
  826.  
  827.     /* put in action number marker; this non-zero number makes sure that
  828.      * find_table_space() knows that this position in chk/nxt is taken
  829.      * and should not be used for another accepting number in another state
  830.      */
  831.     chk[position - 1] = 1;
  832.  
  833.     /* put in end-of-buffer marker; this is for the same purposes as above */
  834.     chk[position] = 1;
  835.  
  836.     /* place the state into chk and nxt */
  837.     state_ptr = &state[1];
  838.  
  839.     for ( i = 1; i <= numecs; ++i, ++state_ptr )
  840.     if ( *state_ptr != 0 )
  841.         {
  842.         chk[position + i] = i;
  843.         nxt[position + i] = *state_ptr;
  844.         }
  845.  
  846.     if ( position + numecs > tblend )
  847.     tblend = position + numecs;
  848.     }
  849.  
  850.  
  851. /* stack1 - save states with only one out-transition to be processed later
  852.  *
  853.  * synopsis
  854.  *   int statenum, sym, nextstate, deflink;
  855.  *   stack1( statenum, sym, nextstate, deflink );
  856.  *
  857.  * if there's room for another state one the "one-transition" stack, the
  858.  * state is pushed onto it, to be processed later by mk1tbl.  If there's
  859.  * no room, we process the sucker right now.
  860.  */
  861.  
  862. stack1( statenum, sym, nextstate, deflink )
  863. int statenum, sym, nextstate, deflink;
  864.  
  865.     {
  866.     if ( onesp >= ONE_STACK_SIZE - 1 )
  867.     mk1tbl( statenum, sym, nextstate, deflink );
  868.  
  869.     else
  870.     {
  871.     ++onesp;
  872.     onestate[onesp] = statenum;
  873.     onesym[onesp] = sym;
  874.     onenext[onesp] = nextstate;
  875.     onedef[onesp] = deflink;
  876.     }
  877.     }
  878.  
  879.  
  880. /* tbldiff - compute differences between two state tables
  881.  *
  882.  * synopsis
  883.  *   int state[], pr, ext[];
  884.  *   int tbldiff, numdifferences;
  885.  *   numdifferences = tbldiff( state, pr, ext )
  886.  *
  887.  * "state" is the state array which is to be extracted from the pr'th
  888.  * proto.  "pr" is both the number of the proto we are extracting from
  889.  * and an index into the save area where we can find the proto's complete
  890.  * state table.  Each entry in "state" which differs from the corresponding
  891.  * entry of "pr" will appear in "ext".
  892.  * Entries which are the same in both "state" and "pr" will be marked
  893.  * as transitions to "SAME_TRANS" in "ext".  The total number of differences
  894.  * between "state" and "pr" is returned as function value.  Note that this
  895.  * number is "numecs" minus the number of "SAME_TRANS" entries in "ext".
  896.  */
  897.  
  898. int tbldiff( state, pr, ext )
  899. int state[], pr, ext[];
  900.  
  901.     {
  902.     register int i, *sp = state, *ep = ext, *protp;
  903.     register int numdiff = 0;
  904.  
  905.     protp = &protsave[numecs * (pr - 1)];
  906.  
  907.     for ( i = numecs; i > 0; --i )
  908.     {
  909.     if ( *++protp == *++sp )
  910.         *++ep = SAME_TRANS;
  911.     else
  912.         {
  913.         *++ep = *sp;
  914.         ++numdiff;
  915.         }
  916.     }
  917.  
  918.     return ( numdiff );
  919.     }
  920.